#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef unsigned int TIME;
class job{
    private:
        TIME enter_time;
        TIME expect_run_time;

        TIME start_time;
        TIME finish_time;
        TIME turnover_time;
        TIME remain_run_time;
        double turnover_time_with_weight;
        double response_ratio;
        bool start;
    public:
        job(TIME st = 0, TIME rt = 0):
            enter_time(st), expect_run_time(rt),start_time(0),finish_time(0),
            turnover_time(0), remain_run_time(rt), turnover_time_with_weight(0.0),response_ratio(0.0), start(false)
            {}
        void Start_Run(TIME now) {
            start = true;
            start_time = now;
        }
        void Finished_Run(TIME now) {
            finish_time = now;
            turnover_time = finish_time - enter_time;
            turnover_time_with_weight = (double)turnover_time / expect_run_time;
        }
        void Compute_Response_Ratio(TIME now) {
            response_ratio = (now - enter_time - (expect_run_time - remain_run_time)) / (double)expect_run_time;
        }
        void Process(TIME now) {
            if (!start) {
                Start_Run(now);
            }
            --remain_run_time;
        }
        void show() {
            printf("This job start at %u, end at %u, whose turnover time is %u, "
                "weighted turnover time is %f\n", start_time, finish_time, turnover_time, turnover_time_with_weight);
        }
        TIME Get_Enter_Time() const {
            return enter_time;
        }
        TIME Get_Expect_Run_Time() const {
            return expect_run_time;
        }
        TIME Get_Finish_Time() const {
            return finish_time;
        }
        TIME Get_Turnover_Time() const {
            return turnover_time;
        }
        TIME Get_Remain_Run_Time() const {
            return remain_run_time;
        }
        double Get_Response_Ratio() const {
            return response_ratio;
        }
        double Get_Turnover_Time_With_Weight() const {
            return turnover_time_with_weight;
        }
};
typedef vector<job> job_stream;
class solution {
    private:
        job_stream jobs;
        unsigned int channel_num;

        double ave_turnover_time;
        double ave_turnover_time_with_weight;
    public:
        solution(const job_stream& jo, unsigned int ch_num = 1): jobs(jo), channel_num(ch_num),
        ave_turnover_time(0.0), ave_turnover_time_with_weight(0.0) {
            sort(jobs.begin(), jobs.end(), [&](job job_a, job job_b) -> bool{
                return job_a.Get_Enter_Time() < job_b.Get_Enter_Time();
            });
        }
        void show() {
            for (int i = 0; i < (int)jobs.size(); ++i) {
                jobs[i].show();
                printf("-----------------------------------------------------------------------------------------------------\n");
            }
            printf("Using this algorithm,  the average turnover time is %f, the average weighted turnover time is %f\n",
                    ave_turnover_time, ave_turnover_time_with_weight);
            puts("");
            puts("");
        }
        void compute_arguments() {
            ave_turnover_time = 0;
            ave_turnover_time_with_weight = 0;
            for (int i = 0; i < (int)jobs.size(); ++i) {
                ave_turnover_time += jobs[i].Get_Turnover_Time();
                ave_turnover_time_with_weight += jobs[i].Get_Turnover_Time_With_Weight();
            }
            ave_turnover_time /= jobs.size();
            ave_turnover_time_with_weight /= jobs.size();
        }
        void first_come_first_served(){
            printf("First come first served algorithm\n");
            TIME now(0);
            for (job& current_job: jobs) {
                now = max(current_job.Get_Enter_Time(), now);
                current_job.Start_Run(now);
                current_job.Finished_Run(now + current_job.Get_Expect_Run_Time());
                now += current_job.Get_Expect_Run_Time();
            }
            compute_arguments();
            show();
        }
        void short_job_first(){
            struct my_comparator {
                bool operator () (const job* job1, const job* job2) const {
                    return job1 -> Get_Remain_Run_Time() > job2 -> Get_Remain_Run_Time();
                }
            };
            printf("Short job first algorithm\n");
            priority_queue<job*, vector<job*>, my_comparator >cache, input_queue;

            int j = 0;
            for (TIME time = 0; time < 1440; ++time) {
                while (j < jobs.size() && jobs[j].Get_Enter_Time() == time) {
                    input_queue.push(&jobs[j++]);
                }
                while (cache.size() < channel_num && !input_queue.empty()) {
                    cache.push(input_queue.top());
                    input_queue.pop();
                }
                if (!cache.empty()) {
                    job* ptr = cache.top();
                    cache.pop();
                    ptr -> Process(time);
                    if (ptr -> Get_Remain_Run_Time() == 0) {
                        ptr -> Finished_Run(time + 1);
                    } else {
                        cache.push(ptr);
                    }
                }
            }
            compute_arguments();
            show();
        }
        void high_response_ratio_first(){
            printf("High response ratio first algorithm\n");
            vector<job*>cache, input_queue;
            int j = 0;
            auto Comparator = [&](job* job1, job* job2) -> bool {
                return job1 -> Get_Response_Ratio() < job2 -> Get_Response_Ratio();
            };
            for (TIME time = 0; time < 1440; ++time) {
                while (j < jobs.size() && jobs[j].Get_Enter_Time() == time) {
                    input_queue.push_back(&jobs[j++]);
                }
                for (int i = 0; i < (int)input_queue.size(); ++i) {
                    input_queue[i] -> Compute_Response_Ratio(time);
                }
                bool in_cache = false;
                sort(input_queue.begin(), input_queue.end(), Comparator);
                while (cache.size() < channel_num && !input_queue.empty()) {
                    cache.push_back(input_queue.back());
                    input_queue.pop_back();
                    in_cache = true;
                }
                if (in_cache) {
                    for (int i = 0; i < (int)cache.size(); ++i) {
                        cache[i] -> Compute_Response_Ratio(time);
                    }
                    sort(cache.begin(), cache.end(), Comparator);
                }
                if (!cache.empty()) {
                    job* ptr = cache.back();
                    ptr -> Process(time);
                    if (ptr -> Get_Remain_Run_Time() == 0) {
                        ptr -> Finished_Run(time + 1);
                        cache.pop_back();
                        for (int i = 0; i < (int)cache.size(); ++i) {
                            cache[i] -> Compute_Response_Ratio(time);
                        }
                        sort(cache.begin(), cache.end(), Comparator);
                    }
                }
            }
            compute_arguments();
            show();
        }
};

int main() {
    job_stream data1{{480, 120}, {530, 50}, {540, 10}, {590, 20}};
    job_stream data2{{600, 30}, {605, 20}, {610, 5}, {620, 10}};

    solution our_solution_for_data1_0(data1, 1);
    solution our_solution_for_data2_0(data2, 2);

    solution our_solution_for_data1_1(data1, 1);
    solution our_solution_for_data2_1(data2, 2);

    solution our_solution_for_data1_2(data1, 1);
    solution our_solution_for_data2_2(data2, 2);

    our_solution_for_data1_0.first_come_first_served();
    our_solution_for_data1_1.short_job_first();
    our_solution_for_data1_2.high_response_ratio_first();

    our_solution_for_data2_0.first_come_first_served();
    our_solution_for_data2_1.short_job_first();
    our_solution_for_data2_2.high_response_ratio_first();

    return 0;
}
